public class MoreThanHalfNum_Solution {
    // 数组中出现次数超过一办的数字
    // https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163?tpId=295&tqId=23271&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3DSQL%25E7%25AF%2587%26topicId%3D295
    public int MoreThanHalfNum_Solution (int[] numbers) {
        // write code here
        int[] hash = new int[10001];
        int targetCount = numbers.length / 2;
        for (int number : numbers) {
            if (++hash[number] > targetCount) {
                return number;
            }
        }
        return -1;
    }

    /**
     * 选举法
     * @param numbers
     * @return
     */
    public int MoreThanHalfNum_Solution2 (int[] numbers) {
        // write code here
        // 数组中超过数组长度一半的数字，那么当遇到相等的数就数量++，否则数量--，那么
        // 最后剩下的一定是出现次数超过一半的数字
        int num = -1;
        int count = 0;
        for (int number : numbers) {
            if (num < 0 || count == 0) {
                num = number;
                count = 1;
            } else if (num == number) {
                count++;
            } else {
                count--;
            }
        }
        return num;
    }
}
